BOJ5642 퀸 게임

퀸 게임

범위를 보면 규칙을 찾아 푸는게 맞는데, 아무리 봐도 규칙은 못찾겠다.

선형 점화식이 존재한다는 믿음을 가지고 벌레캠프를 돌려보면 f(n)-f(n-1)-f(n-k)+f(n-k-1)=0 형태의 점화식을 얻을 수 있다.(i=6에서만 예외적으로 다른 형태가 나오는데, 이는 이후에 다시 언급하겠다.)

식을 정리하면 f(n)-f(n-k)=f(n-1)-f(n-k-1)이 되고, 이는 거리가 k인 두 수열의 원소는 항상 일정한 차이 z=f(n)-f(n-k)를 같는다는 의미다. f(n)=f(n-k)+z라고 보면 이해가 될 것이다.

이제 모든 R에 대해서 k과 z를 구한 db를 만들고 제출하면 된다.

i=6의 경우 벌레캠프에서 다른형태가 나오는데, 얘 또한 위와 같은 특징이 존재할 것이라고 믿고 차이값을 구해보면 존재하는 것을 알 수 있다.